home *** CD-ROM | disk | FTP | other *** search
/ Mac Easy 2010 May / Mac Life Ubuntu.iso / casper / filesystem.squashfs / usr / share / python-support / gnome-games-data / gnome_sudoku / sudoku.py < prev    next >
Encoding:
Python Source  |  2009-04-14  |  31.0 KB  |  832 lines
  1. # -*- coding: utf-8 -*-
  2. import random
  3. import math
  4. import re
  5. from gettext import gettext as _
  6.  
  7. GROUP_SIZE = 9
  8.  
  9. TYPE_ROW = 0
  10. TYPE_COLUMN = 1
  11. TYPE_BOX = 2
  12.  
  13. digit_set = range(1,GROUP_SIZE+1)
  14. sets = [digit_set] * 9
  15.  
  16. def is_set (row):
  17.     if len(row)==len(set(row)): return True
  18.  
  19. def is_sudoku (rows):
  20.     # check rows
  21.     for r in rows:
  22.         if not is_set(r):
  23.             return False
  24.     for i in range(len(rows[0])):
  25.         rw = [r[i] for r in rows]
  26.         if not is_set(rw): return False
  27.     # check boxes
  28.     width = int(math.sqrt(len(rows)))
  29.     # there should be 3x3 boxes, or 4x4 if we got funky, etc.
  30.     # boxes will be indices
  31.     box_coordinates = [[n*width,
  32.                         (n+1)*width] for n in range(width)]
  33.     for x in box_coordinates:
  34.         for y in box_coordinates:
  35.             box = []
  36.             for xrow in [rows[ri] for ri in range(*y)]:
  37.                 for i in range(*x):
  38.                     box.append(xrow[i])
  39.             if not is_set(box): return False
  40.     return True
  41.  
  42. class UnsolvablePuzzle (TypeError):
  43.     pass
  44.  
  45.  
  46. class ConflictError (ValueError):
  47.     
  48.     def __init__ (self, conflict_type, coordinates, value):
  49.         self.args = conflict_type,coordinates,value
  50.         self.type = conflict_type
  51.         self.coordinates = coordinates
  52.         self.x = coordinates[0]
  53.         self.y = coordinates[1]
  54.         self.value = value
  55.  
  56. class AlreadySetError (ValueError):
  57.     pass
  58.     
  59. class SudokuGrid:
  60.     def __init__ (self, grid=False, verbose=False, group_size=9):
  61.         self.grid = []
  62.         self.cols = []
  63.         self.rows = []
  64.         self.boxes = []
  65.         self.group_size = int(group_size)
  66.         self.verbose=False
  67.         self.gen_set = set(range(1,self.group_size+1))
  68.         for n in range(self.group_size):
  69.             self.cols.append(set())
  70.             self.rows.append(set())
  71.             self.boxes.append(set())
  72.             self.grid.append([0]*self.group_size)
  73.         self.box_by_coords = {}
  74.         self.box_coords = {}
  75.         self.calculate_box_coords() # sets box_coords and box_by_coords
  76.         self.row_coords = {}
  77.         for n,row in enumerate([[(x,y) for x in range(self.group_size)] for y in range(self.group_size)]):
  78.             self.row_coords[n]=row
  79.         self.col_coords = {}
  80.         for n,col in enumerate([[(x,y) for y in range(self.group_size)] for x in range(self.group_size)]):
  81.             self.col_coords[n]=col
  82.         if grid:
  83.             if type(grid)==str:
  84.                 g=re.split("\s+",grid)
  85.                 side = int(math.sqrt(len(g)))
  86.                 grid = []
  87.                 for row in range(side):
  88.                     start = row*int(side)
  89.                     grid.append([int(i) for i in g[start:start+side]])
  90.             self.populate_from_grid(grid)
  91.         self.verbose=verbose
  92.  
  93.     def calculate_box_coords (self):
  94.         width = int(math.sqrt(self.group_size))
  95.         box_coordinates = [[n*width,
  96.                             (n+1)*width] for n in range(width)]
  97.         box_num = 0
  98.         for xx in box_coordinates:
  99.             for yy in box_coordinates:
  100.                 self.box_coords[box_num]=[]
  101.                 for x in range(*xx):
  102.                     for y in range(*yy):
  103.                         self.box_by_coords[(x,y)]=box_num
  104.                         self.box_coords[box_num].append((x,y))
  105.                 box_num += 1
  106.  
  107.     def add (self, x, y, val, force=False):
  108.         if not val: pass
  109.         if self._get_(x,y):
  110.             if force:
  111.                 try:
  112.                     self.remove(x,y)
  113.                 except:
  114.                     print 'Strange: problem with add(',x,y,val,force,')'
  115.                     import traceback
  116.                     traceback.print_exc()
  117.             else:
  118.         #FIXME:  This is called when the fill button
  119.         #is clicked multiple times, which causes this exception:
  120.         #raise AlreadySetError
  121.                 return;
  122.         if val in self.rows[y]:
  123.             raise ConflictError(TYPE_ROW,(x,y),val)
  124.         if val in self.cols[x]:
  125.             raise ConflictError(TYPE_COLUMN,(x,y),val)
  126.         box=self.box_by_coords[(x,y)]
  127.         if val in self.boxes[box]:
  128.             raise ConflictError(TYPE_BOX,(x,y),val)
  129.         # do the actual adding
  130.         self.rows[y].add(val)
  131.         self.cols[x].add(val)
  132.         self.boxes[box].add(val)
  133.         self._set_(x,y,val)
  134.  
  135.     def remove (self, x, y):
  136.         val = self._get_(x,y)
  137.         self.rows[y].remove(val)
  138.         self.cols[x].remove(val)
  139.         self.boxes[self.box_by_coords[(x,y)]].remove(val)
  140.         self._set_(x,y,0)
  141.  
  142.     def _get_ (self, x, y): return self.grid[y][x]
  143.  
  144.     def _set_ (self, x, y, val): self.grid[y][x]=val
  145.  
  146.     def possible_values (self, x, y):
  147.         return self.gen_set - self.rows[y] - self.cols[x] - self.boxes[self.box_by_coords[(x,y)]]
  148.  
  149.     def pretty_print (self):
  150.         print 'SUDOKU'
  151.         for r in self.grid:
  152.             for i in r:
  153.                 print i,
  154.             print
  155.         print
  156.  
  157.     def populate_from_grid (self, grid):
  158.         for y,row in enumerate(grid):
  159.             for x,cell in enumerate(row):
  160.                 if cell:
  161.                     self.add(x,y,cell)
  162.  
  163.     def __repr__ (self):
  164.         s = "<Grid\n       "
  165.         grid = []
  166.         for r in self.grid:
  167.             grid.append(" ".join([str(i) for i in r]))
  168.         s += "\n       ".join(grid)
  169.         return s
  170.  
  171.     def calculate_open_squares (self):
  172.         possibilities = {}
  173.         for x in range(self.group_size):
  174.             for y in range(self.group_size):
  175.                 if not self._get_(x,y):
  176.                     possibilities[(x,y)]=self.possible_values(x,y)
  177.         return possibilities
  178.  
  179.     def find_conflicts (self, x, y, val, conflict_type=None):
  180.         '''Find all squares that conflict with value val at position x,y.
  181.         
  182.         If conflict_type is specified, we only find conflicts of given
  183.         type (ROW, COLUMN OR BOX).
  184.         '''
  185.         if conflict_type==TYPE_ROW:
  186.             coords = self.row_coords[y]
  187.         elif conflict_type==TYPE_COLUMN:
  188.             coords = self.col_coords[x]
  189.         elif conflict_type==TYPE_BOX:
  190.             coords = self.box_coords[self.box_by_coords[(x,y)]]
  191.         else:
  192.             coords = (self.row_coords[y]
  193.                       + self.col_coords[x]
  194.                       + self.box_coords[self.box_by_coords[(x,y)]]
  195.                       )
  196.         conflicting_coordinates = []
  197.         for x,y in coords:
  198.             if self._get_(x,y)==val:
  199.                 conflicting_coordinates.append((x,y))
  200.         return conflicting_coordinates
  201.  
  202.     def to_string (self):
  203.         """Output our grid as a string."""
  204.         return " ".join([" ".join([str(x) for x in row]) for row in self.grid])
  205.  
  206. def is_valid_puzzle (p):
  207.     """Check puzzle for basic validity.
  208.     
  209.     This does not check for solvability or ensure a unique
  210.     solution -- it merely checks well-formedness. This should
  211.     provide some protection again file corruption, etc. (i.e. if
  212.     we use this function to check puzzles before handing them out
  213.     to the rest of the app, we'll prevent tracebacks related to
  214.     corrupted puzzles).
  215.     """
  216.     try:
  217.         p = p.replace(' ','')
  218.         assert(len(p.replace(' ',''))==81)
  219.         [int(c) for c in p.replace(' ','')]
  220.     except:
  221.         #import traceback; traceback.print_exc()
  222.         return False
  223.     else:
  224.         return True
  225.  
  226. def sudoku_grid_from_string (s):
  227.     """Given an 81 character string, return a grid."""
  228.     s=s.replace(' ','')
  229.     assert(len(s)<=GROUP_SIZE**2)
  230.     grid = []
  231.     i = 0
  232.     for x in range(GROUP_SIZE):
  233.         row = []
  234.         for y in range(GROUP_SIZE): 
  235.             if len(s) <= i: n = 0
  236.             else: n = s[i]
  237.             try:
  238.                 n = int(n)
  239.             except:
  240.                 n = n or 0
  241.             if n in digit_set:
  242.                 row.append(n)
  243.             else:
  244.                 row.append(0)
  245.             i += 1
  246.         grid.append(row)
  247.     return SudokuGrid(grid)
  248.     
  249.  
  250. class SudokuSolver (SudokuGrid):
  251.     """A SudokuGrid that can solve itself."""
  252.     def __init__ (self, grid=False, verbose=False,group_size=9):        
  253.         self.current_guess = None
  254.         self.initialized=False
  255.         SudokuGrid.__init__(self,grid,verbose=verbose,group_size=group_size)
  256.         self.virgin = SudokuGrid(grid)
  257.         self.guesses = GuessList()
  258.         self.breadcrumbs = BreadcrumbTrail()
  259.         self.backtraces = 0
  260.         self.initialized=True
  261.         self.solved = False
  262.         self.trail = []
  263.  
  264.     def auto_fill_for_xy (self, x, y):
  265.         """Fill the square x,y if possible."""
  266.         possible = self.gen_set - self.rows[y] - self.cols[x] - self.boxes[self.box_by_coords[(x,y)]]
  267.         changed = []
  268.         if len(possible)==1:
  269.             val = possible.pop()
  270.             self.add(x,y,val)
  271.             return ((x,y),val)
  272.         if len(possible)==0:
  273.             return -1
  274.         # check our column...
  275.         for coord_set,filled_set in [(self.col_coords[x],self.cols[x]),
  276.                                      (self.row_coords[y],self.rows[y]),
  277.                                      (self.box_coords[self.box_by_coords[(x,y)]],
  278.                                       self.boxes[self.box_by_coords[(x,y)]])
  279.                                      ]:
  280.             needed_set = self.gen_set - filled_set
  281.             for coord in coord_set:
  282.                 if self._get_(*coord): continue
  283.                 elif (x,y)!=coord:
  284.                     needed_set = needed_set - self.possible_values(*coord)
  285.             if needed_set and len(needed_set)==1:
  286.                 val = needed_set.pop()
  287.                 if val in possible:
  288.                     self.add(x,y,val)
  289.                     return ((x,y),val)
  290.                 else:
  291.                     return -1
  292.             if len(needed_set)>1:
  293.                 return -1
  294.             
  295.     def auto_fill (self):
  296.         changed = []
  297.         try: changed = self.fill_must_fills()
  298.         except UnsolvablePuzzle: return changed
  299.         try:
  300.             changed.extend(self.fill_deterministically())
  301.         finally:
  302.             return changed
  303.  
  304.     def fill_must_fills (self):
  305.         changed = []
  306.         for label,coord_dic,filled_dic in [('Column',self.col_coords,self.cols),
  307.                                            ('Row',self.row_coords,self.rows),
  308.                                            ('Box',self.box_coords,self.boxes)]:
  309.             for n,coord_set in coord_dic.items():
  310.                 needs = dict([(n,False) for n in range(1,self.group_size+1)])
  311.                 for coord in coord_set:
  312.                     val = self._get_(*coord)
  313.                     if val:
  314.                         # We already have this value set...
  315.                         del needs[val]
  316.                     else:
  317.                         # Otherwise, register ourselves as possible
  318.                         # for each number we could be
  319.                         for v in self.possible_values(*coord):
  320.                             # if we don't yet have a possible number, plug ourselves in
  321.                             if needs.has_key(v):
  322.                                 if not needs[v]: needs[v]=coord
  323.                                 else: del needs[v]
  324.                 for n,coords in needs.items():
  325.                     if not coords:
  326.                         raise UnsolvablePuzzle('Missing a %s in %s'%(n,label))
  327.                     else:
  328.                         try:
  329.                             self.add(coords[0],coords[1],n)
  330.                             changed.append((coords,n))
  331.                         except AlreadySetError:
  332.                             raise UnsolvablePuzzle(
  333.                                 "%s,%s must be two values at once!"%(coords)
  334.                                 )
  335.         return changed
  336.     
  337.     def fill_must_fills_2 (self):
  338.         changed = []
  339.         for label,coord_dic,filled_dic in [('Column',self.col_coords,self.cols),
  340.                                            ('Row',self.row_coords,self.rows),
  341.                                            ('Box',self.box_coords,self.boxes)]:
  342.             for n,coord_set in coord_dic.items():
  343.                 needs = dict([(n,[]) for n in range(1,self.group_size+1)])
  344.                 for coord in coord_set:
  345.                     val = self._get_(*coord)
  346.                     if val:
  347.                         del needs[val]
  348.                     else:
  349.                         for v in self.possible_values(*coord):
  350.                             needs[v].append(coord)
  351.                 for n,coords in needs.items():
  352.                     if len(coords)==0:
  353.                         raise UnsolvablePuzzle('Missing a %s in %s'%(n,label))
  354.                     elif len(coords)==1:
  355.                         try:
  356.                             self.add(coords[0][0],coords[0][1],n)
  357.                             changed.append((coords[0],n))
  358.                         except AlreadySetError:
  359.                             raise UnsolvablePuzzle(
  360.                                 "%s,%s must be two values at once!"%(coords[0])
  361.                                 )
  362.         return changed
  363.  
  364.     def fill_must_fills_old (self):
  365.         """If we have a row where only one column can be a 3, it must be a 3.
  366.  
  367.         We raise an error if we discover an impossible situation.
  368.         We return a list of what we've changed
  369.         """
  370.         has_changed = []
  371.         for label,coord_dic,filled_dic in [('Column',self.col_coords,self.cols),
  372.                                            ('Row',self.row_coords,self.rows),
  373.                                            ('Box',self.box_coords,self.boxes)]:
  374.             for n,coord_set in coord_dic.items():
  375.                 values = filled_dic[n] # get set of filled in values for our column
  376.                 needed = self.gen_set - values
  377.                 # A dictionary to track who can fill our various needs...
  378.                 needed_dic = {}
  379.                 for c in needed: needed_dic[c]=[]
  380.                 # just work on the open squares
  381.                 coord_set = filter(lambda coords: not self._get_(*coords),coord_set)                
  382.                 for xy,poss_set in [(c,self.possible_values(*c)) for c in coord_set]:
  383.                     # our set of values we can fill is now greater...
  384.                     values = values|poss_set
  385.                     # track who can fill our needs...
  386.                     for v in poss_set: needed_dic[v].append(xy)
  387.                 # check if our set of fillable values is sufficient
  388.                 if values != self.gen_set:
  389.                     raise UnsolvablePuzzle("Impossible to solve! We are missing %s in %s"%(self.gen_set-values,label))
  390.                 # Check if there are any values for which only one cell will suffice
  391.                 needed_filled_by = needed_dic.items()
  392.                 values_only_one_can_fill = filter(lambda x: len(x[1])==1,needed_filled_by)
  393.                 for v,coords in values_only_one_can_fill:
  394.                     coords = coords[0]
  395.                     if self.verbose: print 'Setting ',coords,v,' by necessity!'
  396.                     if self.verbose: print '(No other item in this ',label,' can be a ',v,')'
  397.                     has_changed.append([(coords[0],coords[1]),v])
  398.                     try:
  399.                         self.add(coords[0],coords[1],v)
  400.                     except AlreadySetError:
  401.                         if self._get_(coords[0],coords[1])==v: pass
  402.                         else:
  403.                             raise UnsolvablePuzzle(
  404.                                 "Impossible to solve! %s,%s must be two values at once!"%(coords)
  405.                                 )
  406.         if self.verbose: print 'fill_must_fills returning ',has_changed
  407.         return has_changed
  408.  
  409.     def scan_must_fills (self):
  410.         """Scan to find how many fill_must_fills we could fill in with
  411.         100% positivity based on the grid as it currently stands (not
  412.         using the *cumulative* results"""        
  413.         # we do this by temporarily disabling the add call
  414.         self.fake_add = True
  415.         self.fake_added = []
  416.         self.fill_must_fills()
  417.  
  418.     def fill_deterministically (self):
  419.         poss = self.calculate_open_squares().items()
  420.         one_choice=filter(lambda x: len(x[1])==1,poss)
  421.         retval = []
  422.         for coords,choices in one_choice:
  423.             if self.verbose: print 'Deterministically adding ',coords,choices
  424.             val = choices.pop()
  425.             self.add(coords[0],coords[1],val)
  426.             retval.append([(coords[0],coords[1]),val])
  427.         if self.verbose: print 'deterministically returning ',retval
  428.         return retval
  429.  
  430.     def solve (self):
  431.         self.auto_fill()
  432.         while not self.guess_least_open_square(): 1
  433.         if self.verbose: print 'Solved!\n', self
  434.         self.solved = True
  435.  
  436.     def solution_finder (self):
  437.         self.auto_fill()
  438.         while not self.guess_least_open_square(): 1
  439.         self.solved=True
  440.         yield tuple([tuple(r) for r in self.grid[0:]])
  441.         while self.breadcrumbs:
  442.             self.unwrap_guess(self.breadcrumbs[-1])
  443.             try:
  444.                 while not self.guess_least_open_square(): 1
  445.             except UnsolvablePuzzle:
  446.                 break
  447.             else:
  448.                 yield tuple([tuple(r) for r in self.grid[0:]])
  449.         yield None
  450.  
  451.     def has_unique_solution (self):
  452.         sf = self.solution_finder()
  453.         sf.next()
  454.         if sf.next(): return False
  455.         else: return True
  456.  
  457.     def find_all_solutions (self):
  458.         solutions = set([])
  459.         sf = self.solution_finder()
  460.         sol = sf.next()
  461.         while sol:
  462.             solutions.add(sol)
  463.             sol = sf.next()
  464.         return solutions
  465.  
  466.     def guess_least_open_square (self):
  467.         # get open squares and check them
  468.         poss = self.calculate_open_squares().items()
  469.         # if there are no open squares, we're done!
  470.         if not poss:
  471.             if self.verbose: print 'Solved!'
  472.             return True
  473.         # otherwise, find the possibility with the least possibilities        
  474.         poss.sort(lambda a,b: len(a[1])>len(b[1]) and 1 or len(a[1])<len(b[1]) and -1 or \
  475.                   a[0]>b[0] and 1 or a[1]<b[1] and -1 or 0)
  476.         least = poss[0]
  477.         # remove anything we've already guessed
  478.         possible_values = least[1] - self.guesses.guesses_for_coord(*least[0])
  479.         if not possible_values:
  480.             if self.breadcrumbs:
  481.                 self.backtraces += 1
  482.                 self.unwrap_guess(self.breadcrumbs[-1])
  483.                 return self.guess_least_open_square()
  484.             else:
  485.                 raise UnsolvablePuzzle("Unsolvable %s.\n \
  486.                 Out of guesses for %s. Already guessed\n \
  487.                 %s (other guesses are %s)"%(self,
  488.                                             least[0],
  489.                                             self.guesses.guesses_for_coord(*least[0]),
  490.                                             self.guesses))
  491.         guess = random.choice(list(possible_values))
  492.         # Create guess object
  493.         guess_obj = Guess(least[0][0],least[0][1],guess)
  494.         if self.breadcrumbs:
  495.             self.breadcrumbs[-1].children.append(guess_obj)
  496.         self.current_guess = None #reset (we're tracked via guess.child)
  497.         self.add(least[0][0],least[0][1],guess)
  498.         self.current_guess = guess_obj # (All deterministic additions
  499.                                        # get added to our
  500.                                        # consequences)
  501.         self.guesses.append(guess_obj)
  502.         self.trail.append(('+',guess_obj))
  503.         self.breadcrumbs.append(guess_obj)
  504.         try:
  505.             filled = self.auto_fill()
  506.         except NotImplementedError:
  507.             self.trail.append('Problem filling coordinates after guess')
  508.             self.unwrap_guess(guess_obj)
  509.             return self.guess_least_open_square()
  510.         if set([]) in self.calculate_open_squares().values():
  511.             self.trail.append('Guess leaves us with impossible squares.')
  512.             self.unwrap_guess(guess_obj)
  513.             return self.guess_least_open_square()
  514.  
  515.     def unwrap_guess (self, guess):
  516.         self.trail.append(('-',guess))
  517.         if self._get_(guess.x,guess.y): self.remove(guess.x,guess.y)
  518.         for consequence in guess.consequences.keys():
  519.             if self._get_(*consequence): self.remove(*consequence)
  520.         for child in guess.children:
  521.             self.unwrap_guess(child)
  522.             if child in self.guesses: self.guesses.remove(child)
  523.         if guess in self.breadcrumbs: self.breadcrumbs.remove(guess)
  524.  
  525.     def print_possibilities (self):
  526.         poss = self.calculate_open_squares()
  527.         poss_list = poss.items()
  528.         poss_list.sort(lambda a,b: len(a[1])>len(b[1]) and 1 or len(a[1])<len(b[1]) and -1 or 0)
  529.         most_poss = len(poss_list[-1][1])
  530.         for y in range(len(self.cols)):
  531.             for x in range(len(self.rows)):
  532.                 if self.grid[y][x]: val = self.grid[y][x]
  533.                 else:
  534.                     val="".join([str(s) for s in poss[(x,y)]])
  535.                 print self.pad(val,most_poss+2),
  536.             for n in range(most_poss + 2): print
  537.  
  538.     def pad (self, n, pad_to):
  539.         n = str(n)
  540.         padding = int(pad_to) - len(n)
  541.         second_half = padding / 2
  542.         first_half = second_half + padding % 2
  543.         return " "*first_half + n + " "*second_half
  544.  
  545.     def add (self, x,y,val,*args,**kwargs):
  546.         if self.current_guess:
  547.             self.current_guess.add_consequence(x,y,val)
  548.         SudokuGrid.add(self,x,y,val,*args,**kwargs)
  549.  
  550.  
  551. class InteractiveSudoku (SudokuSolver):
  552.     """A subclass of SudokuSolver that provides some convenience
  553.     functions for helping along a human.who is in the midst of
  554.     solving."""
  555.     def __init__ (self, grid=False, verbose=False, group_size=9):
  556.         SudokuSolver.__init__(self,grid,verbose,group_size)
  557.  
  558.     def to_string (self):
  559.         return self.virgin.to_string() + '\n' + SudokuSolver.to_string(self)
  560.  
  561.     def find_impossible_implications (self, x, y):
  562.         """Return a list of impossibilities implied by the users actions."""
  563.         row_cells = self.row_coords[y]
  564.         col_cells = self.col_coords[x]
  565.         box = self.box_by_coords[(x,y)]
  566.         box_cells = self.box_coords[box]
  567.         for coord_set in [row_cells,col_cells,box_cells]:
  568.             broken = []
  569.             # just work on the open squares
  570.             coord_set = filter(lambda coords: not self._get_(*coords),coord_set)
  571.             for coords in coord_set:
  572.                 if not self.possible_values(*coords):
  573.                     broken.append(coords)
  574.         return broken
  575.  
  576.     def check_for_completeness (self):
  577.         for r in self.rows:
  578.             if len(r)!=self.group_size:
  579.                 return False
  580.         for c in self.cols:
  581.             if len(c)!=self.group_size:
  582.                 return False
  583.         return True
  584.  
  585.     def is_changed (self):
  586.         return (self.grid!=self.virgin.grid)
  587.  
  588. class DifficultyRating:
  589.     
  590.     very_hard = _('Very Hard')
  591.     hard = _('Hard')
  592.     medium = _('Medium')
  593.     easy = _('Easy')
  594.  
  595.     very_hard_range = (0.75,10)
  596.     hard_range = (0.6,0.75)
  597.     medium_range = (0.45,0.6)
  598.     easy_range = (-10,0.45)
  599.  
  600.     categories = {'very hard':very_hard_range,
  601.                   'hard':hard_range,
  602.                   'medium':medium_range,
  603.                   'easy':easy_range}
  604.  
  605.     ordered_categories = ['easy','medium','hard','very hard']
  606.     label_by_cat = {'easy':easy,
  607.                     'medium':medium,
  608.                     'hard':hard,
  609.                     'very hard':very_hard}
  610.     
  611.     def __init__ (self,
  612.                   fill_must_fillables,
  613.                   elimination_fillables,
  614.                   guesses,
  615.                   backtraces,
  616.                   squares_filled):
  617.         self.fill_must_fillables = fill_must_fillables
  618.         self.elimination_fillables = elimination_fillables        
  619.         self.guesses = guesses
  620.         self.backtraces = backtraces
  621.         self.squares_filled = squares_filled
  622.         if self.fill_must_fillables:
  623.             self.instant_fill_fillable = float(len(self.fill_must_fillables[0]))
  624.         else:
  625.             self.instant_fill_fillable = 0.0
  626.         if self.elimination_fillables:
  627.             self.instant_elimination_fillable = float(len(self.elimination_fillables[0]))
  628.         else:
  629.             self.instant_elimination_fillable = 0.0
  630.         
  631.         self.proportion_instant_elimination_fillable = self.instant_elimination_fillable/self.squares_filled
  632.         # some more numbers that may be crazy...
  633.         self.proportion_instant_fill_fillable = self.instant_fill_fillable/self.squares_filled
  634.         self.elimination_ease = add_with_diminishing_importance(
  635.             self.count_values(self.elimination_fillables)
  636.             )
  637.         self.fillable_ease = add_with_diminishing_importance(
  638.             self.count_values(self.fill_must_fillables)
  639.             )
  640.         self.value = self.calculate()
  641.  
  642.     def count_values (self, dct):
  643.         kk=dct.keys()
  644.         kk.sort()
  645.         return [len(dct[k]) for k in kk]
  646.  
  647.     def calculate (self):
  648.         return 1 - float(self.fillable_ease)/self.squares_filled \
  649.                  - float(self.elimination_ease)/self.squares_filled \
  650.                  + len(self.guesses)/self.squares_filled \
  651.                  + self.backtraces/self.squares_filled
  652.  
  653.     def __repr__ (self): return '<DifficultyRating %s>'%self.value
  654.  
  655.     def pretty_print (self):
  656.         for name,stat in [('Number of moves instantly fillable by elimination',
  657.                            self.instant_elimination_fillable),
  658.                           ('Percentage of moves instantly fillable by elimination',
  659.                            self.proportion_instant_elimination_fillable*100),
  660.                           ('Number of moves instantly fillable by filling',
  661.                            self.instant_fill_fillable),
  662.                           ('Percentage of moves instantly fillable by filling',
  663.                            self.proportion_instant_fill_fillable*100),
  664.                           ('Number of guesses made',
  665.                            len(self.guesses)),
  666.                           ('Number of backtraces', self.backtraces),
  667.                           ('Ease by filling',self.fillable_ease),
  668.                           ('Ease by elimination',self.elimination_ease),
  669.                           ('Calculated difficulty',self.value)
  670.                           ]:
  671.             print name,': ',stat
  672.  
  673.     def value_string (self):
  674.         if self.value > self.very_hard_range[0]: return _(self.very_hard)
  675.         elif self.value > self.hard_range[0]: return _(self.hard)
  676.         elif self.value > self.medium_range[0]: return _(self.medium)
  677.         else: return _(self.easy)
  678.  
  679.     def value_category (self):
  680.         """Get category string, without i18n or capitalization
  681.  
  682.         For use in categorizing category.
  683.         """
  684.         if self.value > self.very_hard_range[0]: return 'very hard'
  685.         elif self.value > self.hard_range[0]: return 'hard'
  686.         elif self.value > self.medium_range[0]: return 'medium'
  687.         else: return 'easy'
  688.  
  689. def get_difficulty_category_name (diff_float):
  690.     return DifficultyRating.label_by_cat.get(
  691.         get_difficulty_category(diff_float),
  692.         '?'
  693.         )
  694.  
  695. def get_difficulty_category (diff_float):
  696.     for category,range in DifficultyRating.categories.items():
  697.         if range[0] <= diff_float < range[1]:
  698.             return category
  699.  
  700. class SudokuRater (SudokuSolver):
  701.  
  702.     def __init__ (self, grid=False, verbose=False, group_size=9):
  703.         self.initialized=False
  704.         self.guessing = False
  705.         self.fake_add = False
  706.         self.fake_additions = []
  707.         self.filled = set([])
  708.         self.fill_must_fillables = {}
  709.         self.elimination_fillables = {}
  710.         self.tier = 0
  711.         SudokuSolver.__init__(self,grid,verbose,group_size)
  712.  
  713.     def add (self,*args,**kwargs):
  714.         if not self.fake_add:
  715.             if self.initialized and not self.guessing:
  716.                 self.scan_fillables()
  717.                 for delayed_args in self.add_me_queue:
  718.                     coords = (delayed_args[0],delayed_args[1])
  719.                     if not self._get_(*coords):
  720.                         SudokuSolver.add(self,*delayed_args)
  721.                 if not self._get_(args[0],args[1]):
  722.                     SudokuSolver.add(self,*args)
  723.                 self.tier += 1
  724.             else:
  725.                 SudokuSolver.add(self,*args,**kwargs)
  726.         else:
  727.             self.fake_additions.append(args)
  728.  
  729.     def scan_fillables (self):
  730.         self.fake_add = True
  731.         # this will now tell us how many squares at current
  732.         # difficulty could be filled at this moment.
  733.         self.fake_additions = []
  734.         try:
  735.             self.fill_must_fills()
  736.         except:
  737.             pass
  738.         self.fill_must_fillables[self.tier]=set(self.fake_additions[:])-self.filled
  739.         self.add_me_queue = self.fake_additions[:]
  740.         self.fake_additions = []
  741.         try:
  742.             self.fill_deterministically()
  743.         except:
  744.             pass
  745.         self.elimination_fillables[self.tier] = set(self.fake_additions[:])-self.filled
  746.         self.filled = self.filled|self.fill_must_fillables[self.tier]|self.elimination_fillables[self.tier]
  747.         self.add_me_queue.extend(self.fake_additions[:])
  748.         self.fake_add = False
  749.  
  750.     def guess_least_open_square (self):
  751.         self.guessing = True
  752.         return SudokuSolver.guess_least_open_square(self)
  753.  
  754.     def difficulty (self):
  755.         if not self.solved: self.solve()
  756.         self.clues = 0
  757.         # Add up the number of our initial clues through some nifty mapping calls
  758.         map(lambda r: map(lambda i: setattr(self,'clues',self.clues.__add__(i and 1 or 0)),
  759.                           r),
  760.             self.virgin.grid)
  761.         self.numbers_added = self.group_size**2 - self.clues
  762.         rating = DifficultyRating(self.fill_must_fillables,
  763.                                   self.elimination_fillables,
  764.                                   self.guesses,
  765.                                   self.backtraces,
  766.                                   self.numbers_added)
  767.         return rating
  768.  
  769.  
  770. class GuessList (list):
  771.     def __init__ (self,*guesses):
  772.         list.__init__(self,*guesses)
  773.  
  774.  
  775.     def guesses_for_coord (self,x,y):
  776.         return set([guess.val for guess in filter(lambda guess: guess.x==x and guess.y==y,self)])
  777.  
  778.     def remove_children (self, guess):
  779.         removed = []
  780.         for g in guess.children:
  781.             if g in self:
  782.                 removed.append(g)
  783.                 self.remove(g)
  784.         return removed
  785.  
  786.     def remove_guesses_for_coord (self, x, y):
  787.         nuking = False
  788.         nuked = []
  789.         for i in range(len(self)-1):
  790.             g = self[i-len(nuked)]
  791.             if g.x==x and g.y == y:
  792.                 nuking=True
  793.             if nuking:
  794.                 self.remove(g)
  795.                 nuked += [g]
  796.         return nuked
  797.     
  798. class BreadcrumbTrail (GuessList):
  799.     def append (self, guess):
  800.         # Raise an error if we add something to ourselves twice
  801.         if self.guesses_for_coord(guess.x,guess.y):
  802.             raise ValueError("We already have crumbs on %s,%s"%(guess.x,guess.y))
  803.         else:
  804.             list.append(self,guess)
  805.  
  806. class Guess:
  807.     def __init__ (self, x, y, val):
  808.         self.x = x
  809.         self.y = y
  810.         self.children = []
  811.         self.val = val
  812.         self.consequences = {}
  813.  
  814.     def add_consequence (self, x, y, val):
  815.         self.consequences[(x,y)]=val
  816.  
  817.     def __repr__ (self):
  818.         s =  "<Guess (%s,%s)=%s"%(self.x,self.y,self.val)
  819.         if self.consequences:
  820.             s +=   " implies: "
  821.             s += ", ".join(["%s->%s"%(k,v) for k,v in self.consequences.items()])
  822.         s += ">"
  823.         return s
  824.  
  825.  
  826. def add_with_diminishing_importance (lst, diminish_by=lambda x: x+1):
  827.     sum = 0
  828.     for i,n in enumerate(lst):
  829.         sum += float(n) / diminish_by(i)
  830.     return sum
  831.  
  832.